1.4 J 与 G-S 收敛

定理 I-1-4 (1)（对角占优定理） 严格对角占优矩阵、不可约弱对角占优矩阵，是非奇异矩阵.

证明

1. 严格对角占优矩阵是非奇异矩阵.

$\det(\bm A) = 0$ $\bm A \bm x = \bm 0$ $\bm x = (\soneto{x}{n})\trans$ ，

$\vqty{x_k} = \d\max_{1 \le i \le n} \vqty{x_i}$ $k$ $\dsum_{j=1}^n a_{kj} x_j = 0$ 有，

| a_{k k} x_{k} | = | \sum_{j = 1, j \neq k}^{n} a_{k j} x_{j} | \leq \sum_{j = 1, j \neq k}^{n} | a_{k j} | | x_{j} | \leq | x_{k} | \sum_{j = 1, j \neq k}^{n} | a_{k j} |,

$\vqty{a_{kk}} \le \dsum_{j=1, j \ne k}^n \vqty{a_{kj}}$ ，矛盾.

2. 不可约弱对角占优矩阵是非奇异矩阵.

$\det(\bm A) = 0$ $\bm A \bm x = \bm 0$ $\bm x = (\soneto{x}{n})\trans$ ，

2.1 对于弱对角占优矩阵，如下定义集合，并证明集合非空.

J := {k ∣ (\forall i : | x_{k} | \geq | x_{i} |) \land (\exists j : | x_{k} | > | x_{j} |)},

$J$ $\vqty{x_1} = \vqty{x_2} = \cdots = \vqty{x_n}$ ，

$\forall i$ $\dsum_{j=1}^n a_{ij} x_j = 0$ 有

| a_{i i} x_{i} | = | \sum_{j \neq i} a_{i j} x_{j} | \leq \sum_{j \neq i} | a_{i j} | | x_{j} | = | x_{j} | \sum_{j \neq i} | a_{i j} |,

$\forall i \colon \vqty{a_{ii}} \le \dsum_{j \ne i} \vqty{a_{ij}}$ ，与弱对角占优矩阵矛盾.

2.2 对于不可约矩阵，进一步证明非奇异性.

{\begin{cases} | a_{k k} | | x_{k} | \leq \sum_{j \neq k} | a_{k j} | | x_{j} |, \\ | a_{k k} | \geq \sum_{j \neq k} | a_{k j} |, \end{cases} \Rightarrow \sum_{j \neq k} | a_{k j} | \leq \sum_{j \neq k} | a_{k j} | \frac{| x_{j} |}{| x_{k} |},

$\forall j \pqty{\vqty{x_j} < \vqty{x_k}} \colon a_{kj} = 0$ $\forall k \in J, \forall j \notin J \colon a_{kj} = 0$ ，

从而可排列为分块上三角矩阵，矛盾. 证毕.

备注 $\left| \begin{array}{ccc} 1 & 0 & -1 \\ 1 & 2 & 0 \\ -3 & 0 & 3 \\ \end{array} \right| = 0$ .

定理 i-1-4 (2)（充分条件） $\bm A \bm x = \bm b$ 的 J 迭代法与 GS 迭代法均收敛.

证明

$\bm G = (\bm D - \bm L) \inv \bm U$ 的特征值，即下述方程的解

\begin{aligned} 0 & = \det (λ I - G) \\ = \det (λ I - (D - L)^{- 1} U) \\ = \det ((D - L)^{- 1}) \det (λ (D - L) - U), \end{aligned}

$\det((\bm D - \bm L)\inv) \ne 0$ $\det(\lambda(\bm D - \bm L) - \bm U) = 0$ 的根. 记

\begin{matrix} C := λ (D - L) - U = | \begin{matrix} λ a_{11} & a_{12} & \dots & a_{1 n} \\ λ a_{21} & λ a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ λ a_{n 1} & λ a_{n 2} & \dots & λ a_{n n} \end{matrix} |, \end{matrix}

$\vqty{\lambda} \ge 1$ 时，

\begin{aligned} | c_{i i} | & = | λ a_{i i} | > | λ | \sum_{j \neq i} | a_{i j} | \\ \geq \sum_{j = 1}^{i - 1} | λ a_{i j} | + \sum_{j = i + 1}^{n} | a_{i j} | = \sum_{j \neq i} | c_{i j} |, \end{aligned}

$\bm C$ $\det(\bm C) \ne 0$ $\forall \lambda \colon \vqty{\lambda} < 1$ .